// https://www.lintcode.com/problem/heapify

public class Solution {
    /*
     * @param A: Given an integer array
     * @return: nothing
     */
    public void heapify(int[] A) {
        // write your code here
        for (int i = A.length - 1; i >= 0; --i) {
            int j = i;
            int min_pos = j;
            while (j < A.length) {
                int left = j * 2 + 1;
                int right = j * 2 + 2;
                if ((left < A.length) && (A[left] < A[min_pos])) {
                    min_pos = left;
                }
                if ((right < A.length) && (A[right] < A[min_pos])) {
                    min_pos = right;
                }
                if (j != min_pos) {
                    int tmp = A[j];
                    A[j] = A[min_pos];
                    A[min_pos] = tmp;
                    j = min_pos;
                } else {
                    break;
                }
            }
        }
    }
}